package cn.bellychang.leetcode.question034;

/**
 * @author ChangLiang
 * @date 2021/3/22
 */
public class Solution {

    public int[] searchRange(int[] nums, int target) {

        if (nums == null || nums.length==0) {
            return new int[]{-1, -1};
        }

        int[] result = new int[2];
        result[0] =lowerFloor(nums, target);
        result[1] = upperCeil(nums, target);
        return result;
    }

    private int lowerFloor(int[] nums, int target) {

        int begin = 0;
        int end = nums.length - 1;
        while (begin < end) {
            int mid = ((end - begin) >> 1) + begin;
            if (nums[mid] < target) {
                begin = mid + 1;
            } else {
                end = mid;
            }
        }
        return nums[end] == target ? end : -1;
    }

    private int upperCeil(int[] nums, int target){
        int begin = 0;
        int end = nums.length - 1;
        while (begin < end) {
            int mid = ((end - begin + 1) >> 1) + begin;
            if(nums[mid] <= target){
                begin = mid;
            }else{
                end = mid - 1;
            }
        }
        return nums[end] == target? end: -1;
    }
}
